package Javafoundation;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class Topo2 {
    private List<VertexNode> vexList;
    public void createGraph1()
    {
        VertexNode v0 = new VertexNode(0, 1, null);
        EdgeNode v0e0 = new EdgeNode(1, 0, null);
        EdgeNode v0e1 = new EdgeNode(2, 0, null);
        v0.setFirstEdge(v0e0);
        v0e0.setNext(v0e1);
        VertexNode v1 = new VertexNode(0, 1, null);
        EdgeNode v1e0 = new EdgeNode(3, 0, null);
        EdgeNode v1e1 = new EdgeNode(4, 0, null);
        v1.setFirstEdge(v1e0);
        v1e0.setNext(v1e1);
        VertexNode v2 = new VertexNode(1, 2, null);
        EdgeNode v2e0 = new EdgeNode(3, 0, null);
        EdgeNode v2e1 = new EdgeNode(5, 0, null);
        v2.setFirstEdge(v2e0);
        v2e0.setNext(v2e1);
        VertexNode v3 = new VertexNode(2, 3, null);
        EdgeNode v3e0 = new EdgeNode(5, 0, null);
        v3.setFirstEdge(v3e0);
        VertexNode v4 = new VertexNode(1, 4, null);
        EdgeNode v4e0 = new EdgeNode(5, 0, null);
        v4.setFirstEdge(v4e0);

        VertexNode v5 = new VertexNode(3, 5, null);

        vexList = new ArrayList<>();
        vexList.add(v0);
        vexList.add(v1);
        vexList.add(v2);
        vexList.add(v3);
        vexList.add(v4);
        vexList.add(v5);
    }

    public void createGraph2(){
        VertexNode v0 = new VertexNode(0, 0, null);
        EdgeNode v0e0 = new EdgeNode(1, 0, null);
        EdgeNode v0e1 = new EdgeNode(2, 0, null);
        v0.setFirstEdge(v0e0);
        v0e0.setNext(v0e1);

        VertexNode v1 = new VertexNode(1, 1, null);
        EdgeNode v1e0 = new EdgeNode(5, 0, null);
        v1.setFirstEdge(v1e0);

        VertexNode v2 = new VertexNode(1, 2, null);
        EdgeNode v2e0 = new EdgeNode(3, 0, null);
        v2.setFirstEdge(v2e0);


        VertexNode v3 = new VertexNode(2, 3, null);
        EdgeNode v3e0 = new EdgeNode(4, 0, null);
        v3.setFirstEdge(v3e0);


        VertexNode v4 = new VertexNode(1, 4, null);
        EdgeNode v4e0 = new EdgeNode(5, 0, null);
        EdgeNode v4e1 = new EdgeNode(6, 0, null);
        v4.setFirstEdge(v4e0);
        v4e0.setNext(v4e1);

        VertexNode v6 = new VertexNode(1, 6, null);
        EdgeNode v6e0 = new EdgeNode(7, 0, null);
        v6.setFirstEdge(v6e0);

        VertexNode v7 = new VertexNode(1, 7, null);
        EdgeNode v7e0 = new EdgeNode(3, 0, null);
        v7.setFirstEdge(v7e0);

        VertexNode v5 = new VertexNode(2, 5, null);


        vexList = new ArrayList<>();
        vexList.add(v0);
        vexList.add(v1);
        vexList.add(v2);
        vexList.add(v3);
        vexList.add(v4);
        vexList.add(v5);
        vexList.add(v6);
        vexList.add(v7);

    }


    public boolean topologicalSort() {
        int count = 0;
        Stack<Integer> stack = new Stack<>();
        for (int i = 0;i < vexList.size(); i++) {
            vexList.get(i).setIn(0);
        }

        for (int i = 0;i < vexList.size(); i++) {
            EdgeNode edge = vexList.get(i).getFirstEdge();
            while (edge != null) {
                VertexNode vex = vexList.get(edge.getAdjvex());
                vex.setIn(vex.getIn() + 1);
                edge = edge.getNext();
            }
        }
        for (int i = 0;i < vexList.size(); i++) {
            if (vexList.get(i).getIn() == 0) {
                stack.push(i);
            }
        }



        while (!stack.isEmpty()) {
            int vexIndex = stack.pop();
            System.out.print(vexIndex+1 + "  ");
            count++;
            EdgeNode edge = vexList.get(vexIndex).getFirstEdge();
            while (edge != null) {
                int adjvex = edge.getAdjvex();
                VertexNode vex = vexList.get(adjvex);
                vex.setIn(vex.getIn() - 1);
                if (vex.getIn() == 0)
                    stack.push(adjvex);
                edge = edge.getNext();
            }
        }

        if (count != vexList.size())
            return false;
        else
            return true;
    }

    public static void main(String[] args) {
        Topo2 topological = new Topo2();
        topological.createGraph1();
        boolean success = topological.topologicalSort();
        if (success) {
            System.out.println("\n成功，无环图");
        }else {
            System.out.println("\n失败，有环图");
        }

        Topo2 topological2 = new Topo2();
        topological2.createGraph2();
        boolean success2 = topological2.topologicalSort();
        if (success2) {
            System.out.println("\n成功，无环图");
        }else {
            System.out.println("\n失败，有环图");
        }
    }
}
